class Solution
{
public:
    ListNode *sortList(ListNode *head)
    {
        if (!head || !head->next)
            return head;

        /**
         *  1. 将整个链表，不断的分为 前、后【两半】【子链表】
         *  - 1) [head, slow]
         *  - 2) [slow+1, end]
         */
        ListNode *pre = head;
        ListNode *slow = head;
        ListNode *fast = head;
        while (fast && fast->next) // 只需要判断 fast 和 fast->next
        {
            pre = slow;              // pre 记录每一次 slow
            slow = slow->next;       // slow 每次想走走【1步】
            fast = fast->next->next; // fast 每次想走走【2步】
        }

        // 2.【断开】slow->next
        pre->next = nullptr;

        // 3. 再继续【递归】划分子链表，并调用【合并】链表算法
        return mergeTwoList(
            sortList(head), // 递归排序 [head, slow]
            sortList(slow)  // 递归排序 [slow+1, end]
        );
    }

    // 【合并】两个【有序】链表
    ListNode *mergeTwoList(ListNode *h1, ListNode *h2)
    {
        if (!h1)
            return h2;
        if (!h2)
            return h1;

        if (h1->val < h2->val)
        {
            h1->next = mergeTwoList(h1->next, h2);
            return h1;
        }
        else
        {
            h2->next = mergeTwoList(h1, h2->next);
            return h2;
        }
    }
};
